Internet Info 1993/Internet Info CD-ROM (Walnut Creek) (1993).iso/inet/ien/ien-46

Text File | 1988-12-01 | 22KB | 704 lines

Internet Notebook Section 2.3.3.15                                Clark, Cohen
IEN No. 46                                                          June, 1978








A PROPOSAL FOR ADDRESSING AND ROUTING IN THE INTERNET

David D. Clark
Laboratory for Computer Science
Massachusetts Institute of Technology

Danny Cohen
USC/Information Sciences Institute





1.   Introduction

     Within the internet, there is a need for both addressing and routing

information as part of every packet.  Using the distinction articulated by

John Shoch (1), we take the address of a packet to be where the packet is

destined, and the route, the specification of how the packet will get there.

Currently, an internet header contains only an address, and the route is

derived implicitly from that address.  That addressing/routing strategy is

quite suitable given the current internet topology, but two problems may arise

as the internet continues to grow.  First, unless the internet experiment is

truncated artificially, it can be expected to continue, as has the ARPANET,

for some period of time, in which case the number of networks involved may

grow to exceed the size of the field allocated to number them.  Second, as the

topology grows more complex, it may not always be possible to deduce the

desired or effective route from the address.  This proposal attempts to

address those two problems.


Internet Notebook Section 2.3.3.15                                Clark, Cohen
IEN No. 46                                                          June, 1978


2.   Addressing of Networks

     The current internet header has space to name 256 networks.  The

assumption, at least for the time being, is that any network entering the

internet will be assigned one of these numbers.  While it is not likely that a

great number of large nets, such as the ARPANET, will join the internet, the

trend toward local area networking suggests that a very large number of small

networks can be expected in the internet in the not too distant future.  We

should thus begin to prepare for the day when there are more than 256 networks

participating in the internet.

     To cope with this problem, we propose that the top level entity named in

an internet address not be a single network, but, optionally, an aggregate of

networks which we will refer to as a region.  Thus, an address now begins with

a region number, perhaps followed by a network number, in turn followed by

network dependent fields.  Large networks, such as the ARPANET, will

presumably continue to be a region unto themselves.  In fact, all of the

currently existing networks in the internet can be viewed as regions, which

means that no reimplementation is required if the concept of regions is

accepted.  However, in the future, as more and more nets enter the internet,

we can, at our discression, lump various networks together into regions.  Put

another way, a network can only join the internet by first joining a region.

     In fact, the concept of a region was always available to the internet,

although in an informal manner.  The structure of a network address was

unspecified except that it began with a fixed size field naming the network.

It was always permissible to use the component of the internet address next

after the network field to identify a subnet of the named network.  Making

more explicit this hierarchy of regions and networks is important because, as


                                      2

Internet Notebook Section 2.3.3.15                                Clark, Cohen
IEN No. 46                                                          June, 1978


we discussed above, the address is used not only as an address but as a basis

for deriving a default route.  We must thus consider how, using the addressing

structure of regions and nets within regions, the address can be used to

generate an effective and unambiguous route.


3.   Default Routing

     Currently, every gateway in the internet knows how to generate a route to

every network.  If the number of networks grows substantially above 100 or

200, the gateways can no longer be expected to understand this much

information.  One of the major purposes of the region concept is to control

the amount of information which every gateway must know.  This scheme would

imply that an arbitrary gateway now only need to know how to reach every

region, but need not be concerned with routing to the individual network

within a distant region.  Only for gateways connected to or completely inside

a particular region would be necessary to understand how to route packets to

all of the networks within the region.

     Let us consider an example of how these regions might be used.  There are

already two local networks at M.I.T., with more on the way.  These might quite

properly be considered as one region.  That would imply that a gateway located

in England need not be concerned with the internal structure of the local

networks at M.I.T.  If M.I.T. were one region, such a gateway would merely

need to know how to reach M.I.T.  Only when the packet has reached a gateway

connecting to one of the nets at M.I.T., would it be necessary to begin to

worry about how to reach the correct local network.  It is possible that

deriving the route in this manner will not produce the optimum route; the

packet may arrive at a gateway to M.I.T. which leads to the wrong local



                                      3

Internet Notebook Section 2.3.3.15                                Clark, Cohen
IEN No. 46                                                          June, 1978


network, but presumably this is an acceptable inefficiency.  (We will return

later to consider what might be done if it is not an acceptable inefficiency.)

More generally, this example suggests that the success of deriving routes from

addresses depends critically on the way networks are grouped together to form

regions.  A region containing two networks, one in California and the other in

England, is not structured in such a way that effective routes can be derived

from the network address alone.  A naive gateway, routing its packet only to

the region without regard to the particular network for which the packet is

destined, may discover that the packet has been routed to the wrong side of

the world.  In fact, it is probable, in most cases, that regions should be

connected.  If not, it may be impossible to get a packet from one part of the

region to the other, since the packet will have to leave the region in order

to do so and may encounter a gateway which, not understanding anything about

the network structure of the region, blindly sends the packet back to the part

of the region from which it came.  If, however, the appropriate gateways can

be specially trained, there is nothing to prevent a disjoint region, and in

particular circumstances it may be quite appropriate.


4.   Source Routing

     In the previous section, it was shown that an internet address of the

form <region, network,...> could be used to derive a default route for a

packet, much as a route is now derived by the gateways from the current

internetwork address.  Can we presume that this route will always be

sufficient, even if it is not optimal?  Unfortunately, in a few cases we

cannot.  First, it is easy to imagine circumstances in which the default route

is hopelessly inefficient.  A network may be connected by gateways to several



                                      4

Internet Notebook Section 2.3.3.15                                Clark, Cohen
IEN No. 46                                                          June, 1978


regions, even though for addressing purposes it is identified as belonging to

one particular region.  To send a packet to that region in order to reach the

network may grossly lengthen the path of the packet.  As we said before, this

problem can be minimized by proper use of the region mechanism, but we cannot

expect the region mechanism to be perfect.  Second, it may be necessary to

route a packet in such a way that it explicitly does not go through certain

networks.  For example, speech packets may be hopelessly delayed if they

inadvertantly travel by a network involving a satellite.  It may be necessary

to ensure that speech packets travel by some network with lower bandwidth but

better response characteristics.

     How can the internet come up with better routing information in those

cases where it is required?  In many cases, additional intelligence can be

built into the gateways.  What is required is that gateways not immediately

adjacent to a region be prepared to understand the network field as well as

the region field of packets destined to that region.  This is analogous to

something which happened in the telephone system, where a central office

originating a phone call will usually examine only the area code in order to

generate a route, but may, if it detects a particular area code, then further

examine the destinations central office to discover if use of a particular

optomized route is applicable.  Building this additional routing knowledge

into the gateways is very desirable in general, since it means that it will

apply to all packets.  However, we cannot expect all routing information to be

embedded in the gateways.  First, in order to solve the problem offered above

of properly routing the speech packet, it would be necessary for the gateways

to base their routing decisions on type of service information.  This sounds

like a rather complex decision for the gateways, especially since type of


                                      5

Internet Notebook Section 2.3.3.15                                Clark, Cohen
IEN No. 46                                                          June, 1978


service is not well understood.  Second, network topology will change with

time, and it is not reasonable to expect that all gateways will be constantly

updated.  Thus, we can expect the situation where only the originator of the

packet has sufficient information to specify the proper route.

     The solution which has been proposed in the past to cope with this is to

replace the address in the packet whith a route, called a source route since

it is provided by the source of the packet.  The disadvantage of having a

route in a packet instead of an address is that the concept of an address is

very useful one.  For example, for accounting purposes it may be necessary to

note the source and destination of a packet as it passes through a transit

net.  Clearly, it is desirable that the source and destination be uniquely

identified for this purpose, something not easily done if the source and

destination are specified only by a route.  Thus, we propose that the address

continue to be the primary piece of information in the packet, but that it be

possible to include, in addition, an optional source route.  This new internet

option field will, if present, be used by the gateways instead of the default

route which would normally be derived from the address.

     We do not propose, in this report, a specific syntax for the option

field.  However, we make the following general observations.  The source route

should be structured in such a way that it need not contain more information

than that required to augment the defficiencies in the default route.  Thus,

for example, it should be possible to source route a packet into a particular

region, then specify that the default route should be used to get from there

to some other region, and then specify additional explicit source information.

In a later section we propose a particular semantics for source routes.




                                      6

Internet Notebook Section 2.3.3.15                                Clark, Cohen
IEN No. 46                                                          June, 1978


5.  Migration

     What is the relationship between the scheme proposed here and the current

internet header with a fixed size address field?  Happily, adoption of the

addressing strategy involving regions together with the optional internet

source route implies no immediate upheaval to packet formats or gateway code.

Currently, every network is a region, and every gateway thus contains code for

doing inter-region routing.  Eventually, gateways will want to be modified as

follows.  When a region finally is defined which contains more than one

network, then gateways inside that region will need to understand an

additional component of the internet address.  Presumably, since different

regions may have a different number of networks, we can expect the size of the

network field to differ between regions.  Thus, unless gateway code is

rewritten for different regions, it will be necessary to write code which can

deal, eventually, with a variable size component of the address.  The address

itself, however, can reasonably be a fixed size, since it is merely an address

and not a route.  In fact, it seems that the field as specified for the

current internet header is sufficient in size, although perhaps marginally so.

Given that certain implementations of this header already exist, I would

suggest that the correct field size in 3.1 be accepted unless strong

complaints are heard from someone in the near future.

     The next step in adopting this scheme, after the gateways have learned

that for certain regions they must also look at some additional address bits,

is to arrange that gateways selectively use this additional information, even

when it is for a region for which they are not immediately adjacent.  This

facility, discussed above, can be used to provide more efficient routing than

the default which would otherwise result from simplistic use of the address


                                      7

Internet Notebook Section 2.3.3.15                                Clark, Cohen
IEN No. 46                                                          June, 1978


information.  The technical problem here is not implementation of additional

gateway code for address manipulation, but rather the development of proper

policies for dissemination of routing information so that the appropriate

gateways are correctly informed of the routing decisions to make.

     The third and final step in adoption of this scheme is the implementation

in the gateways and hosts of the new internet option which specifies explicit

source routes.  Presumably, the general mechanism for dealing with internet

option fields will already exist, so this is not a major upheaval of the code

which parses an internet header.  The only issue related to parsing is that,

as the packet flows from gateway to gateway the source route will need to be

modified to indicate which portion has already been used.  This can either be

done by physically rewriting the route into the option field, or by providing

a pointer into the field as part of the option.  The pointer field has the

advantage that it does not destroy the route, so that it can be used to

backtrack to the source, which is an important feature.

    There are two reasons why it is desirable to be able to use a source route

in reverse.  First, the recipient of the packet may have no idea how to get

back to the source.  Second, and more relevant, if the route has been formed

incorrectly, a gateway may receive a packet and have no idea how to forward

it, because the next component of the route is nonsense.  If that intermediate

gateway cannot figure out how to get an error message back to the originating

host, packets sent with malformed routes will appear to fall into black holes.

It is very difficult to debug systems with black holes.  Thus, reversability

of routes is very important.

     The need for modification implies the option should not be checksummed as

part of an end-to-end checksum.  The packet will also contain an address which


                                      8

Internet Notebook Section 2.3.3.15                                Clark, Cohen
IEN No. 46                                                          June, 1978


can be used by the eventual recipient to confirm that the packet is indeed

destined for him.  The address field can be checksummed, and under certain

circumstances even encrypted.


6.   Semantics of Source Routes

     We view the internet as being composed of three physical entities:

networks, gateways, and hosts, and one logical entity, a region, which is an

aggregate of networks.  The default route algorithm examines the region and,

optionally, the network within this region, and selects from a table the

appropriate network and gateway on that network to which to send the packet.

Thus, if the route followed by a packet were written out in advance, it would

be an alternating concatination of network names and gateway names, finally

terminating with a network name followed by a host name.  For symmetry, one

should also precede the source route with the name of the originating host, to

allow the route to be used in reverse.  Thus, an initial structure for

internet source routes might look as follows:


          H,N,G,N,G,N,G,N,...,G,N,H

          where H is a host identifier,

          N is a network identifier,

          G is a gateway identifier.

Each gateway, on receiving this route, finds his position in the route using

the pointer into the route, updates the pointer to indicate the next gateway

which is to receive the packet, and then routes the packet through the

specified network to the next gateway.

     The source route as shown above always specifies the complete route.  For

many cases this degree of specificity is not necessary.  For example, once a


                                      9

Internet Notebook Section 2.3.3.15                                Clark, Cohen
IEN No. 46                                                          June, 1978


packet has been routed part of its way, the default route may then be

effective.  This generalization means that instead of specifying the

particular network which is used as we pass from one gateway to the next, a

default route can be used between two particular points in the route.  Thus,

we propose a more general form of a source route, as follows:


          <source route>:=<source><step>...<destination>


     The source route takes the packet from the source to a sequence of

gateways to the destination.  The progress from each of these specified points

to the next is a step.


          <step>:=<explicit route step>|<default route step>

          <explicit route step>:= RNG


     If we are concerned with the exact route between one gateway and the

next, we specify the step in this form, naming the particular network that is

to be used.  A sequence of explicit route steps can thus connect two gateways

not immediately adjacent.


          <default route step>:=<starting net><ending net>G

          <starting net>,<ending net>:= RN


     If the particular route to the next specified point is not critical, then

the default route step is used.  The originating gateway will generate a route

to the network addressed by <ending net>.  That net may be any distance away

in the internet; intermediate gateways in this step will again generate the

default route from <ending net> until the specified gateway G is reached,

which will end the step.  <starting net> is required so that the route can be


                                      10

Internet Notebook Section 2.3.3.15                                Clark, Cohen
IEN No. 46                                                          June, 1978


used in reverse.  It must specify the network address of the gateway,

originating this step.


          <destination>:= RNH|RNRNH


     The destination is in fact the final step and as such can be either

explicit or default.  Thus it has two forms, with the interpretation of the

step with the equivalent form.

     Note that while the string representing the source route is generated as

a sequence of "forward" steps, there is another grammar that generates the

same strings as a sequence of "reverse" steps.  Also, in the <explicit route

step>, the intervening network is identified using a full network address,

including the region.  In fact, any shorthand network identifier can be used,

so long as it is unambiguously interpretable by the gateway at each end of the

step.


7.   Uniqueness of Names

     Hosts will often be attached to more than one network.  Thus, hosts may

have more than one internet address.  As long as the only routing algorithm is

default routes based on addresses, there will be a strong desire to use these

additional names to generate better routes.  While this is fine in the short

run, functions such as accounting will be easier to implement if hosts have a

single unique address.  To this end, when the route option is implemented we

expect that it will be appropriate to address a host in only one way, and

specify a route additionally.







                                      11

Internet Notebook Section 2.3.3.15                                Clark, Cohen
IEN No. 46                                                          June, 1978


REFERENCES:


   (1)  Shoch, J.F., "A Note on Inter-Networking Naming, Addressing, and
        Routing," Xerox Palo Alto Research Center, Palo Alto, California,
        INTERNET Notebook, Note No. 19, Section 2.3.3.5, January 1978.















































                                      12